Surrogate ranking for very expensive similarity queries.

Mixture models for learning low%2Ddimensional roles in high%2Ddimensional data.

The DataPath system a data%2Dcentric analytic processing engine for large data warehouses.

Evaluation of probabilistic threshold queries in MCDB.

MCDB%2DR Risk Analysis in the Database.
Enterprises often need to assess and manage the risk arising from uncertainty in their data. Such uncertainty is typically modeled as a probability distribution over the uncertain data values, specified by means of a complex (often predictive) stochastic model. The probability distribution over data values leads to a probability distribution over database query results, and risk assessment amounts to exploration of the upper or lower tail of a query-result distribution. In this paper, we extend the Monte Carlo Database System to efficiently obtain a set of samples from the tail of a query-result distribution by adapting recent “Gibbs cloning ” ideas from the simulation literature to a database setting. 1.
A LRT framework for fast spatial anomaly detection.

A LRT framework for fast spatial anomaly detection.

Turbo%2DCharging Estimate Convergence in DBO.
DBO is a database system that utilizes randomized algorithms to give statistically meaningful estimates for the final answer to a multi-table, disk-based query from start to finish during query execution. However, DBO’s “time ’til utility ” (or “TTU”; that is, the time until DBO can give a useful estimate) can be overly large, particularly in the case that many database tables are joined in a query, or in the case that a join query includes a very selective predicate on one or more of the tables, or when the data are skewed. In this paper, we describe Turbo DBO, which is a prototype database system that can answer multi-table join queries in a scalable fashion, just like DBO. However, Turbo DBO often has a much lower TTU than DBO. The key innovation of Turbo DBO is that it makes use of novel algorithms that look for and remember “partial match ” tuples in a randomized fashion. These are tuples that satisfy some of the boolean predicates associated with the query, and can possibly be grown into tuples that actually contribute to the final query result at a later time. 1.
Sampling%2Dbased estimators for subset%2Dbased queries.

Guessing the extreme values in a data set a Bayesian method and its applications.

Robust Stratified Sampling Plans for Low Selectivity Queries.

The DBO database system.
We demonstrate our prototype of the DBO database system. DBO is designed to facilitate scalable analytic processing over large data archives. DBO’s analytic processing performance is competitive with other database systems; however, unlike any other existing research or industrial system, DBO maintains a statistically meaningful guess to the final answer to a query from start to finish during query processing. This guess may be quite accurate after only a few seconds or minutes, while answering a query exactly may take hours. This can result in significant savings in both user and computer time, since a user can abort a query as soon as he or she is happy with the guess ’ accuracy. 1.
A bayesian mixture model with linear regression mixing proportions.

The DBO database system.
We demonstrate our prototype of the DBO database system. DBO is designed to facilitate scalable analytic processing over large data archives. DBO’s analytic processing performance is competitive with other database systems; however, unlike any other existing research or industrial system, DBO maintains a statistically meaningful guess to the final answer to a query from start to finish during query processing. This guess may be quite accurate after only a few seconds or minutes, while answering a query exactly may take hours. This can result in significant savings in both user and computer time, since a user can abort a query as soon as he or she is happy with the guess ’ accuracy. 1.
MCDB a monte carlo approach to managing uncertain data.

Confidence bounds for sampling%2Dbased group by estimates.

Scalable approximate query processing with the DBO engine.

Materialized Sample Views for Database Approximation.
We consider the problem of creating a sample view of a database table. A sample view is an indexed, materialized view that permits efficient sampling from an arbitrary range query over the view. Such “sample views ” are very useful to applications that require random samples from a database: approximate query processing, online aggregation, data mining, and randomized algorithms are a few examples. Our core technical contribution is a new file organization called the ACE Tree that is suitable for organizing and indexing a sample view. One of the most important aspects of the ACE Tree is that it supports online random sampling from the view. That is, at all times, the set of records returned by the ACE Tree constitutes a statistically random sample of the database records satisfying the relational selection predicate over the view. Our paper presents experimental results that demonstrate the utility of the ACE Tree.
Learning correlations using the mixture%2Dof%2Dsubsets model.

Reference%2Dbased indexing for metric spaces with costly distance measures.

Maintaining very large random samples using the geometric file.



Scalable approximate query processing with the DBO engine.

A Bayesian Method for Guessing the Extreme Values in a Data Set.
For a large number of data management problems, it would be very useful to be able to obtain a few samples from a data set, and to use the samples to guess the largest (or smallest) value in the entire data set. Min/max online aggregation, top-k query processing, outlier detection, and distance join are just a few possible applications. This paper details a statistically rigorous, Bayesian approach to attacking this problem. Just as importantly, we demonstrate the utility of our approach by showing how it can be applied to two specific problems that arise in the context of data management. 1.
Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing.
Many aspects of the data integration problem have been considered in the literature: how to match schemas across different data sources, how to decide when different records refer to the same entity, how to efficiently perform the required entity resolution in a batch fashion, and so on. However, what has largely been ignored is a way to efficiently deploy these existing methods in a realistic, distributed enterprise integration environment. The straightforward use of existing methods often requires that all data be shipped to a coordinator for cleaning, which is often unacceptable. We develop a set of randomized algorithms that allow efficient application of existing entity resolution methods to the answering of aggregate queries over data that have been distributed across multiple sites. Using our methods, it is possible to efficiently generate aggregate query results that account for duplicate and inconsistent values scattered across a federated system. 
Online Random Shuffling of Large Database Tables.

Conditional Anomaly Detection.
Abstract: Anomaly detection methods can be very useful in identifying unusual or interesting patterns in data. A recently proposed conditional anomaly detection framework extends anomaly detection to the problem of identifying anomalous patterns on a subset of attributes in the data. The anomaly always depends (is conditioned) on the value of remaining attributes. The work presented in this paper focuses on instance-based methods for detecting conditional anomalies. The methods rely on the distance metric to identify examples in the dataset that are most critical for detecting the anomaly. We investigate various metrics and metric learning methods to optimize the performance of the instance-based anomaly detection methods. We show the benefits of the instance-based methods on two real-world detection problems: detection of unusual admission decisions for patients with the community-acquired pneumonia and detection of unusual orders of an HPF4 test that is used to confirm Heparin induced thrombocytopenia - a life-threatening condition caused by the Heparin therapy.
The partitioned exponential file for database storage management.

Materialized Sample Views for Database Approximation.
We consider the problem of creating a sample view of a database table. A sample view is an indexed, materialized view that permits efficient sampling from an arbitrary range query over the view. Such “sample views ” are very useful to applications that require random samples from a database: approximate query processing, online aggregation, data mining, and randomized algorithms are a few examples. Our core technical contribution is a new file organization called the ACE Tree that is suitable for organizing and indexing a sample view. One of the most important aspects of the ACE Tree is that it supports online random sampling from the view. That is, at all times, the set of records returned by the ACE Tree constitutes a statistically random sample of the database records satisfying the relational selection predicate over the view. Our paper presents experimental results that demonstrate the utility of the ACE Tree.
New Sampling%2DBased Estimators for OLAP Queries.
One important way in which sampling for approximate query processing in a database environment differs from traditional applications of sampling is that in a database, it is feasible to collect accurate summary statistics from the data in addition to the sample. This paper describes a set of sampling-based estimators for approximate query processing that make use of simple summary statistics to to greatly increase the accuracy of sampling-based estimators. Our estimators are able to give tight probabilistic guarantees on estimation accuracy. They are suitable for low or high dimensional data, and work with categorical or numerical attributes. Furthermore, the information used by our estimators can easily be gathered in a single pass, making them suitable for use in a streaming environment. 1
Closest%2DPoint%2Dof%2DApproach Join for Moving Object Histories.
In applications that produce a large amount of data describing the paths of moving objects, there is a need to ask questions about the interaction of objects over a long recorded history. In this paper, we consider the problem of computing joins over massive moving object histories. The particular join that we study is the &#034;Closest-Point-OfApproach &#034; join, which asks: Given a massive moving object history, which objects approached within a distance `d&#039; of one another? We carefully consider several relatively obvious strategies for computing the answer to such a join, and then propose a novel, adaptive join algorithm which naturally alters the way in which it computes the join in response to the characteristics of the underlying data.
Outlier detection by sampling with accuracy guarantees.
An effective approach to detect anomalous points in a data set is distance-based outlier detection. This paper describes a simple sampling algorithm to efficiently detect distancebased outliers in domains where each and every distance computation is very expensive. Unlike any existing algorithms, the sampling algorithm requires a fixed number of distance computations and can return good results with accuracy guarantees. The most computationally expensive aspect of estimating the accuracy of the result is sorting all of the distances computed by the sampling algorithm. This enables interactive-speed performance over the most expensive distance computations. The paper’s algorithms were tested over two domains that require expensive distance functions as well as ten additional real data sets. The experimental study demonstrates both the efficiency and effectiveness of the sampling algorithm in comparison with the state-of-theart algorithm and the reliability of the accuracy guarantees. 1.
Reference%2Dbased Indexing of Sequence Databases.
We consider the problem of similarity search in a very large sequence database with edit distance as the similarity measure. Given limited main memory, our goal is to develop a reference-based index that reduces the number of costly edit distance computations in order to answer a query. The idea in reference-based indexing is to select a small set of reference sequences that serve as a surrogate for the other sequences in the database. We consider two novel strategies for selecting references as well as a new strategy for assigning references to database sequences. Our experimental results show that our selection and assignment methods far outperform competitive methods. For example, our methods prune up to 20 times as many sequences as the Omni method, and as many as 30 times as many sequences as frequency vectors. Our methods also scale nicely for databases containing many and/or very long sequences. 1.
The Sort%2DMerge%2DShrink join.
One of the most common operations in analytic query processing is the application of an aggregate function to the result of a relational join. We describe an algorithm called the Sort-Merge-Shrink (SMS) Join for computing the answer to such a query over large, disk-based input tables. The key innovation of the SMS join is that if the input data are clustered in a statistically random fashion on disk, then at all times, the join provides an online, statistical estimator for the eventual answer to the query as well as probabilistic confidence bounds. Thus, a user can monitor the progress of the join throughout its execution and stop the join when satisfied with the estimate’s accuracy or run the algorithm to completion with a total time requirement that is not much longer than that of other common join algorithms. This contrasts with other online join algorithms, which either do not offer such statistical guarantees or can only offer guarantees so long as the input data can fit into main memory.
A Disk%2DBased Join With Probabilistic Guarantees.
One of the most common operations in analytic query processing is the application of an aggregate function to the result of a relational join. We describe an algorithm for computing the answer to such a query over large, disk-based input tables. The key innovation of our algorithm is that at all times, it provides an online, statistical estimator for the eventual answer to the query, as well as probabilistic confidence bounds. Thus, a user can monitor the progress of the join throughout its execution and stop the join when satisfied with the estimate’s accuracy, or run the algorithm to completion with a total time requirement that is not much longer than other common join algorithms. This contrasts with other online join algorithms, which either do not offer such statistical guarantees or can only offer guarantees so long as the input data can fit into core memory. 1
Relational Confidence Bounds Are Easy With The Bootstrap.
Statistical estimation and approximate query processing have become increasingly prevalent applications for database systems. However, approximation is usually of little use without some sort of guarantee on estimation accuracy, or “confidence bound. ” Analytically deriving probabilistic guarantees for database queries over sampled data is a daunting task, not suitable for the faint of heart, and certainly beyond the expertise of the typical database system end-user. This paper considers the problem of incorporating into a database system a powerful “plug-in ” method for computing confidence bounds on the answer to relational database queries over sampled or incomplete data. This statistical tool, called the bootstrap, is simple enough that it can be used by a database programmer with a rudimentary mathematical background, but general enough that it can be applied to almost any statistical inference problem. Given the power and ease-of-use of the bootstrap, we argue that the algorithms presented for supporting the bootstrap should be incorporated into any database system which is intended to support analytic processing. 1
Online Estimation For Subset%2DBased SQL Queries.
The largest databases in use today are so large that answering a query exactly can take minutes, hours, or even days. One way to address this problem is to make use of approximation algorithms. Previous work on online aggregation has considered how to give online estimates with everincreasing accuracy for aggregate functions over relational join and selection queries. However, no existing work is applicable to online estimation over subset-based SQL queries–those queries with a correlated subquery linked to an outer query via a NOT EXISTS, NOT IN, EXISTS, orIN clause (other queries such asEXCEPT and INTERSECT can also be seen as subset-based queries). In this paper we develop algorithms for online estimation over such queries, and consider the difficult problem of providing probabilistic accuracy guarantees at all times during query execution. 1
Finding the most interesting correlations in a database how hard can it be%3F.

Online Maintenance of Very Large Random Samples.
Random sampling is one of the most fundamental data management tools available. However, most current research involving sampling considers the problem of how to use a sample, and not how to compute one. The implicit assumption is that a “sample ” is a small data structure that is easily maintained as new data are encountered, even though simple statistical arguments demonstrate that very large samples of gigabytes or terabytes in size can be necessary to provide high accuracy. No existing work tackles the problem of maintaining very large, disk-based samples from a data management perspective, and no techniques now exist for maintaining very large samples in an online manner from streaming data. In this paper, we present online algorithms for maintaining on-disk samples that are gigabytes or terabytes in size. The algorithms are designed for streaming data, or for any environment where a large sample must be maintained online in a single pass through a data set. The algorithms meet the strict requirement that the sample always be a true, statistically random sample (without replacement) of all of the data processed thus far. Our algorithms are also suitable for biased or unequal probability sampling. 1
Playing hide%2Dand%2Dseek with correlations.

Robust Estimation With Sampling and Approximate Pre%2DAggregation.
The majority of data reduction techniques for approximate query processing (such as wavelets, histograms, kernels, and so on) are not usually applicable to categorical data. There has been something of a disconnect between research in this area and the reality of database data; much recent research has focused on approximate query processing over ordered or numerical attributes, but arguably the majority of database attributes are categorical: country, state, job_title, color, sex, department, and so on. This paper considers the problem of approximation of aggregate functions over categorical data, or mixed categorical/numerical data. We propose a method based upon random sampling, called Approximate Pre-Aggregation (APA). The biggest drawback of sampling for aggregate function estimating is the sensitivity of sampling to attribute value skew, and APA uses several techniques to overcome this sensitivity. The increase in accuracy using APA compared to “plain vanilla ” sampling is dramatic. For SUM and AVG queries, the relative error for random sampling alone is more than 700 % greater than for sampling with APA. Even if stratified sampling techniques are used, the error is still between 28 % and 175 % greater than for APA. 1
Bridging the Gap between Response Time and Energy%2DEfficiency in Broadcast Schedule Design.

Out From Under the Trees.
This work is motivated by the observation that hard disk seek capability per byte of storage has declined exponentially for decades, and yet most popular access structures are still based on basic ideas proposed 30 years ago. These access structures are typically seek-intensive. In this paper, we propose a new paradigm for data access and organization called the linear file, which aims to drastically reduce disk seeks during query and  update evaluation, by organizing data as a set of ongoing, on-disk sorts. In a linear file, updates are processed quickly, structures are 100% packed, and data are carefully organized on disk to reduce seeks among disk pages. Since the linear file is a general template for data organization, in this paper we benchmark T1SM and T2SM, two specific instantiations for use with one-dimensional and spatial data, respectively.  1. Contact author  Paper ID: 261  1  1 Introduction  The B-tree and other closely related structures have been the foundation for physi...
Lossy Reduction for Very High Dimensional Data.
We consider the use of data reduction techniques for the problem of approximate query answering. We focus on applications for which accurate answers selective queries are required, and for which the data is very high dimensional (having hundreds or perhaps thousands of dimensions). We carefully examine the assumptions underlying many existing reduction techniques. To ensure both speed and accuracy, we show that these methods assume statistical characteristics that very high dimensional datasets do not in general possess. We present a new data reduction method that does not suffer from these limitations, called the RS Kernel. We demonstrate the effectiveness of this method for answering difficult, highly selective queries over high dimensional data using several real datasets.  1. Contact Author: (404) 894-7008  1  1 Introduction  Statistical models of very large databases can be effective tools for efficient, accurate approximate query answering [1][2][5][7][14][15]. The ubiquity of da...
Maintaining a Large Spatial Database with T2SM.

Efficient Data Allocation over Multiple Channels at Broadcast Servers.

Maintaining a Large Spatial Database with T2SM.

The Computational Complexity of High%2DDimensional Correlation Search.

Approximate Query Answering in High%2DDimensional Data Cubes.
Data mining work has been successful in both compressing  and modeling large data sets with many values.  However, the problem of high-dimensions has  not been sufficiently addressed. In our work, we  develop a new data reduction method that aims to  speed subsequent data analysis by efficiently constructing  a high-dimensional, joint probability distribution.  This distribution summarizes the data by  identifying subspaces that are the most unexpected.  That is, we find regions that have many more or many  fewer data points than expected. Our proposed data  reduction method is defined with the inherent computational  complexity of high-dimensional search in  mind, and lends itself to efficient approximation. We  present results illustrating the effectiveness of this  method in finding accurate approximate answers to  high dimensional data cube queries.  1 Problem Statement  Huge, high-dimensional, numerical and categorical datasets provide a difficult set of problems for knowledge dis...
A Novel Index Supporting High Volume Data Warehouse Insertion.
While the desire to support fast, ad hoc query processing for large data warehouses has motivated the recent introduction of many new indexing structures, with a few notable exceptions (namely, the LSM-Tree [4] and the Stepped Merge Method [1]) little attention has been given to developing new indexing schemes that allow fast insertions. Since additions to a large warehouse may number in the millions per day, indices that require a disk seek (or even a significant fraction of a seek) per insertion are not acceptable. In this paper, we offer an alternative to the B+-tree called the Y-tree for indexing huge warehouses having frequent insertions. The Y-tree is a new indexing structure supporting both point and range queries over a single attribute, with retrieval performance comparable to the B+-tree. For processing insertions, however, the Y-tree may exhibit a speedup of 100 times over batched insertions into a B+-tree. 1
Computing Program Modularizations Using the k%2DCut Method.

